package com.leetcode.sort.basic_sort;

import java.util.Random;

/**
 * @author Dennis Li
 * @date 2020/9/9 23:57
 */
public class QuickSort extends Sort {

    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            int[] res = new Random().ints(100, 0, 100).toArray();
//            sort3Way(res, 0, res.length - 1);
            sort(res);
            boolean result = isSorted(res);
            System.out.println(i + ":" + result);
        }
    }

    public static boolean isSorted(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1])
                return false;
        }
        return true;
    }

    public static void sort(int[] arr) {
        QuickSort quick = new QuickSort();
        quick.sort(arr, 0, arr.length - 1);
    }

    private void sort(int[] arr, int lo, int hi) {
        if (lo >= hi) return;

        int p = partition(arr, lo, hi);

        sort(arr, lo, p - 1);
        sort(arr, p + 1, hi);
    }

    private int partition(int[] arr, int lo, int hi) {
        int i = lo, j = hi + 1;
        int pivot = arr[lo];
        while (true) {
            // i可以去到头
            while (arr[++i] < pivot && i < hi) ;
            // j 要与锚定点区分
            while (arr[--j] < pivot && j > lo) ;
            if (i >= j)
                break;
            swap(arr, i, j);
        }
        swap(arr, lo, j);
        return j;
    }

    // 三向切分的快速排序
    //对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。
    //三向切分快速排序对于有大量重复元素的随机数组可以在线性时间内完成排序

    // 空间复杂度主要是由递归树的深度决定的 -- 最优是O(logn)，最差是O(n)
    public static void sort3Way(int[] nums, int lo, int hi) {
        if (hi <= lo) return;
        int lt = lo, i = lo + 1, gt = hi;
        int pivot = nums[lo];
        while (i <= gt) {
            int cmp = Integer.compare(nums[i], pivot);
            // 比基数小
            if (cmp < 0) {
                // lt 恒指向参照物，而此时i与lt指向相同，所以需要将i+1，让其跳转到需要分类的区间
                swap(nums, lt++, i++);
            } else if (cmp > 0) {
                // 比基数大
                // 这里引入插入排序的思想。缩小区间
                swap(nums, gt--, i);
            } else {
                // 和基数相等！注意是和基数相等，所以才不用移动lt
                i++;
            }
        }
        // lt ~ gt 这一部分是相等的元素，不需要进行排序
        sort3Way(nums, lo, lt - 1);
        sort3Way(nums, gt + 1, hi);
    }

    static class Practice extends Sort {

        public static void main(String[] args) {
            long start = System.currentTimeMillis();
            for (int i = 0; i < 10; i++) {
                int[] nums = generateArray(100000);
                sort(nums, 0, nums.length - 1);
                System.out.println(isSorted(nums));
            }
            System.out.println(System.currentTimeMillis() - start);
        }

        private static void sort(int[] nums, int lo, int hi) {
            if (lo >= hi) return;
            int lt = lo, i = lo + 1, gt = hi;
            int pivot = nums[lo];
            while (i <= gt) {
                int cmp = Integer.compare(nums[i], pivot);
                if (cmp < 0) {
                    swap(nums, lt++, i++);
                } else if (cmp > 0) {
                    swap(nums, gt--, i);
                } else {
                    i++;
                }
            }
            sort(nums, lo, lt - 1);
            sort(nums, gt + 1, hi);
        }

        private static void sort2(int[] nums, int lo, int hi) {
            if (lo >= hi) return;
            int p = partition(nums, lo, hi);
            sort2(nums, lo, p - 1);
            sort2(nums, p + 1, hi);
        }

        private static int partition(int[] nums, int lo, int hi) {
            int i = lo, j = hi + 1;
            int pivot = nums[lo];
            while (true) {
                while (nums[++i] < pivot && i < hi);
                while (nums[--j] > pivot && j > lo);
                if (i >= j) break;
                swap(nums, i, j);
            }
            swap(nums, lo, j);
            return j;
        }

    }
}
